With the advent of electronic design automation (EDA), the design of complex hardware systems no longer begins with a hardware circuit diagram. Instead, circuit design typically begins with a software program that describes the behavior or functionality of the hardware system. In one exemplary approach, the behavior or functionality of an electronic circuit design may be described using a hardware-description language (HDL) (e.g., VHDL, Verilog, or other such language). Circuit designers may use EDA logical synthesis tools to generate a netlist that comprises a list of the elements in the circuit and the interconnections between them. At the logical synthesis stage, designers can generate alternative architectures for an integrated circuit by modifying certain design constraints (e.g., the clock, the number and type of data path elements, and/or the desired number of clock cycles for performing a certain function). During the physical design stage, the netlist and information about the layout of the circuit can be used to determine the placement of the various elements of the circuit and the routing. The physical circuit embodying the design can then be created.
As part of the EDA process, the timing characteristics of the circuit design are typically evaluated. This may be done during logical synthesis and before detailed placement and routing of the circuit. Timing analysis may also be performed during the physical synthesis stage of the EDA process following detailed placement and routing. Timing analysis typically involves evaluating whether the circuit design tolerates signal delays inherent in the design. For example, for a given clock speed, a particular circuit design may require that a signal propagate through a circuit path or circuit element within a certain amount of time in order to function properly. During the timing analysis, the actual delay time for a particular path or element is determined and compared with the time required by the path or element. This comparison can be used to determine whether the signal delay time along the path (the path delay) meets the required time delay for that path. The amount by which the actual delay time differs from the required delay time can be referred to generally as “slack.” As used herein, slack may be positive, indicating that the signal propagates faster (i.e., in less time) than required and that there is some spare time built into the timing. Slack may also be negative, indicating that the signal does not propagate in sufficient time to meet the timing requirements of the circuit. Or slack may be zero, indicating that the signal propagates in sufficient time to meet the required time delay, but with no spare time remaining. Consequently, a zero or positive slack indicates that the path or element complies with timing requirements, and a negative slack indicates that the circuit path or element fails to meet the timing requirements at the clock speed at which it is desired to operate the circuit
In a technique referred to collectively as “retiming,” circuit elements can be repositioned, reconfigured, or possibly removed from the circuit design in order to reduce or increase the delay of a particular circuit path. Retiming is desirably performed so that the functionality of the circuit is unchanged. That is, the observable behavior of the circuit after retiming should be identical to the behavior of the circuit before retiming. Ordinarily, retiming involves the movement of sequential elements (e.g. flip-flops, latches, registers, or other such clocked elements) across logic instances (e.g., combinational logic, look-up-tables (LUTs), etc.). Retiming can be performed, for example, to minimize the clock period required to operate the circuit, reduce the number of registers in the circuit, and/or to reduce the power consumed by the circuit. For example, if retiming is performed to minimize the clock period, one or more sequential elements can be relocated in the circuit such that all circuit paths have zero or positive slack. Alternatively, the clock speed may be slowed to increase the required delay times so that all circuit paths of the circuit have zero or positive slack.
In order to be effective, retiming techniques should be as accurate as possible and reliably predict the actual performance of the integrated circuit. Many conventional retiming techniques, however, do not accurately account for circuit delay caused by interconnect. With the continuous trend toward smaller feature sizes and faster clock speeds, the delay caused by the interconnect of a circuit has become a major concern. Indeed, as much as 70% of the delay in a circuit may be caused by interconnect. Accordingly, effective retiming operations that can analyze and account for interconnect delay is important to effective circuit design. Moreover, with the increasing popularity of field programmable gate arrays (FPGAs), retiming techniques that can account for the architectural and structural constraints inherent to FPGA designs are desirable.